package lc20240601;

import lc20240521.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class ZigzagBFS {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(9);
        root.right=new TreeNode(20,new TreeNode(15),new TreeNode(7));

        ZigzagBFS zigzagBFS=new ZigzagBFS();
        System.out.println(zigzagBFS.zigzagLevelOrder1(root));
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if (root==null){
            return list;
        }
        Deque<TreeNode> queue=new ArrayDeque<>();
        Deque<Integer> temp;
        boolean flag=false;
        queue.add(root);
        while (!queue.isEmpty()){
            int size= queue.size();
            List<Integer> list1=new ArrayList<>();
            flag=!flag;
            temp=new ArrayDeque<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur=queue.poll();
                if (cur.left!=null){
                    queue.add(cur.left);
                }
                if (cur.right!=null){
                    queue.add(cur.right);
                }
                temp.add(cur.val);
            }
            if (!flag){
                while (!temp.isEmpty()){
                    list1.add(temp.removeLast());
                }
            }else{
                while (!temp.isEmpty()){
                    list1.add(temp.removeFirst());
                }
            }
            list.add(list1);
        }
        return list;
    }

    //优化
    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if (root==null){
            return list;
        }
        Deque<TreeNode> queue=new ArrayDeque<>();
        queue.add(root);

        //设置一个转向的标志
        boolean flag=false;
        while (!queue.isEmpty()){
            int size= queue.size();
//            List<Integer> list1=new ArrayList<>();
            flag=!flag;
            Deque<Integer> temp=new ArrayDeque<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur=queue.poll();
                if (flag){
                    //从队列末尾往前插入
                    temp.offerLast(cur.val);
                }else{
                    //从队头开始往末尾插入。
                    temp.offerFirst(cur.val);
                }

                if (cur.left!=null){
                    queue.add(cur.left);
                }
                if (cur.right!=null){
                    queue.add(cur.right);
                }
            }
            list.add(new ArrayList<>(temp));
        }
        return list;
    }
}
